Introduction

Due to their ubiquitous use, block ciphers are often called the work horse of cryptography. They operate on plaintexts of a fixed size, called blocks, and produce ciphertexts of the same length.

Definition: Block Cipher

A block cipher is a Shannon cipher $(Enc, Dec)$ with identical message and ciphertext spaces, i.e. $M \equiv C$ , such that for every key $k \in K$ the encryption function $Enc_{k}$ is a pseudorandom permutation over $M$ and the decryption function $Dec_{k}$ is its inverse.

Definition Breakdown

The construction of a block cipher is rooted in pseudorandom permutations (PRPs), hence why the plaintexts (also known as the data blocks) and the ciphertexts are always of the same length. Furthermore, since every PRP is required to be invertible, there is a natural implementation for the decryption function which is simply the inverse of the PRP used for encryption.

Implementation

In practice, block ciphers are built by iteration in the so-called rounds using a round function and each block cipher uses a different number of rounds.

The first phase of encryption is the key expansion. The key $k$ (also called the master key) is expanded into several round keys $k_{1}, k_{2}, ..., k_{d}$ of size $n^{'}$ - one for each round. At each round, the round key $k_{i}$ is used in the round function $R$ together with the output of the previous round. The first round uses the initial plaintext as input.

Similarly, decryption also begins by expanding the master key $k$ into the same set of round keys $k_{1}, k_{2}, ..., k_{d}$ . This time, however, the keys are used in reverse order together with the inverse of the round function - $R^{- 1}$ .

The reason for constructing practical block ciphers is two fold. First, encryption and decryption use more or less the same algorithm which makes it easy to create specialised hardware for them, drastically speeding up these operations.

Note

The Advanced Encryption Standard (AES) is the most ubiquitous block cipher in the world and most CPUs have dedicated hardware and instructions for it.

Second, the round function $R$ can be a very simple operation and it might not even be considered secure on its own! Heuristic evidence suggests that the security of a block cipher comes from the iteration of the round function and not necessarily from the round function itself.